//: Playground - noun: a place where people can play

import UIKit

/**
 * 栈
 * 1.栈是后进先出的结构
 * 2.在iOS开发中, 如果要再App中添加撤销操作(比如删除图片、恢复删除图片), 那么栈是首选数据结构
 * 3.无论是在面试时还是在写App时, 主要关注栈的这几个基本操作: push, pop, isEmpty, peek 和 size
 */
protocol Stack {
    // 持有元素类型
    associatedtype Element
    
    // 是否为空
    var isEmpty: Bool {get}
    // 栈的大小
    var size: Int {get}
    //栈顶元素
    var peek: Element? {get}
    
    // 进栈
    mutating func push(_ newElement: Element);
    // 出栈
    mutating func pop() -> Element?
}

struct IntegerStack: Stack {
    typealias Element = Int;
    
    private var stack = [Element]();
    var isEmpty: Bool {
        return stack.isEmpty;
    }
    var size: Int {
        return stack.count;
    }
    var peek: Int? {
        return stack.last;
    }
    
    mutating func push(_ newElement: Int) {
        stack.append(newElement);
    }
    
    mutating func pop() -> Int? {
        return stack.popLast();
    }
}

/**
 * 队列
 * 1.队列是先进先出的结构
 * iOS开发中多线程的GCD和NSOperationQueue就是基于队列实现的
 * 关于队列只需要关注enqueue, dequeue, isEmpty, peek 和 size等操作
 */
protocol Queue {
    // 持有元素的类型
    associatedtype Element;
    
    // 是否为空
    var isEmpty: Bool {get}
    // 队列的大小
    var size: Int {get}
    // 队首元素
    var peek: Element? {get}
    
    // 入队
    mutating func enqueue(_ newElement: Element);
    // 出队
    mutating func dequeue() -> Element?
}

struct IntergerQueue: Queue {
    typealias Element = Int;
    
    private var left = [Element]();
    private var right = [Element]();
    var isEmpty: Bool {
        return left.isEmpty && right.isEmpty;
    }
    var size: Int {
        return left.count + right.count;
    }
    var peek: Int? {
        return left.isEmpty ? right.first : left.last;
    }
    
    mutating func enqueue(_ newElement: Int) {
        right.append(newElement);
    }
    
    mutating func dequeue() -> Int? {
        if (left.isEmpty) {
            left = right.reversed();
            right.removeAll();
        }
        return left.popLast();
    }
}

// 用栈实现队列
struct MyQueue {
    var stackA: IntegerStack;
    var stackB: IntegerStack;
    
    var isEmpty: Bool {
        return stackA.isEmpty && stackB.isEmpty;
    }
    
    var peek: Any? {
        mutating get {
            shift();
            return stackB.peek;
        }
    }
    
    var size: Int {
        get {
            return stackA.size + stackB.size;
        }
    }
    
    init() {
        stackA = IntegerStack();
        stackB = IntegerStack();
    }
    
    mutating func enqueue(object: Int) {
        stackA.push(object);
    }
    
    mutating func dequeue() -> Int? {
        shift();
        return stackB.pop();
    }
    
    fileprivate mutating func shift() {
        if (stackB.isEmpty) {
            while (!stackA.isEmpty) {
                stackB.push(stackA.pop()!);
            }
        }
    }
}

// 用队列实现栈
struct MyStack {
    var queueA: IntergerQueue;
    var queueB: IntergerQueue;
    
    init() {
        queueA = IntergerQueue();
        queueB = IntergerQueue();
    }
    
    var isEmpty: Bool {
        return queueA.isEmpty && queueB.isEmpty;
    }
    var peek: Int? {
        mutating get {
            shift();
            let peekObj = queueA.peek;
            queueB.enqueue(queueA.dequeue()!);
            swap();
            return peekObj;
        }
    }
    
    var size: Int {
        return queueA.size;
    }
    
    mutating func push(object: Int) {
        queueA.enqueue(object);
    }
    
    mutating func pop() -> Int? {
        shift();
        let popObj = queueA.dequeue();
        swap();
        return popObj;
    }
    
    private mutating func shift() {
        while (queueA.size != 1) {
            queueB.enqueue(queueA.dequeue()!);
        }
    }
    
    private mutating func swap() {
        (queueA, queueB) = (queueB, queueA);
    }
}

// 简化文件路径
func simplifyPath(path: String) -> String {
    // 用数组来实现栈的功能
    var pathStack = [String]();
    
    // 拆分原路径
    let paths = path.components(separatedBy: "/");
    
    for path in paths {
        // 对于"."我们直接跳过
        guard (path != ".") else {
            continue;
        }
        
        // 对于".."使用pop操作
        if (path == "..") {
            if (pathStack.count > 0) {
                pathStack.removeLast();
            }
        // 对于空数组的特殊情况
        } else if (path != "") {
            pathStack.append(path);
        }
    }
    
    // 将栈中的内容转化为优化后的新路径
    let res = pathStack.reduce(into: "") { (total, dir) in
        return "\(total)/\(dir)";
    }
    
    return res.isEmpty ? "/" : res;
}

let path = "/abc/cde/fgh/../ijk/../mno/";
let simplify = simplifyPath(path: path);



